\subsection{Definitions}
We use the notation \( [n] \) for \( \qty{1, \dots,n} \).
For a set \( X \) and \( k \in \mathbb N \), we define \( X^{(k)} = \qty{Y \subseteq X \mid \abs{Y} = k} \).
\begin{definition}
	A \emph{graph} is a pair \( (V, E) \), where \( V \) is a set of \emph{vertices} and \( E \) is a set of \emph{edges} where \( E \subseteq V^{(2)} \).
	We use the notation \( V(G) \) to denote the set of vertices and \( E(G) \) to denote the set of edges, where \( G = (V, E) \) is a graph.
	We define \( \abs{G} = \abs{V(G)} \), and \( e(G) = \abs{E(G)} \).
\end{definition}
\begin{example}
	The complete graph on \( n \) vertices, denoted \( K_n \), is the graph with \( V = [n] \) and \( E = V^{(2)} \).
\end{example}
Note that we sometimes use juxtaposition of names of vertices to denote an edge between them, so \( 13 \) represents the edge \( \qty{1, 3} \).
\begin{remark}
	Edges are undirected. There are no edges from a vertex to itself. Edges between vertices are unique if they exist.
	Most of the graphs covered in this course are finite.
\end{remark}
\begin{example}
	The empty graph on \( n \) vertices, denoted \( \overline K_n \), is the graph with vertex set \( V = [n] \) and \( E = \varnothing \).
\end{example}
\begin{example}
	The path of length \( n \), denoted \( P_n \), is the graph with vertex set \( V = [n+1] \) and edge set \( E = \qty{\qty{1,2},\dots,\qty{n,n+1}} \).
\end{example}
\begin{example}
	The cycle of length \( n \), denoted \( C_n \), is the graph with vertex set \( V = [n] \) and edge set \( E = \qty{\qty{1,2}, \dots, \qty{n-1,n}, \qty{n,1}} \).
\end{example}
\begin{definition}
	Let \( G \) be a graph, \( x \in V(G) \).
	The \emph{neighbourhood} of \( x \) in \( G \) is
	\[ N_G(x) = \qty{y \in V(G) \mid \qty{x,y} \in E(G)} \]
	If \( y \) is a neighbour of \( x \), we write \( x \sim y \).
\end{definition}
Note that \( \sim \) is irreflexive and not transitive in general.
\begin{definition}
	The \emph{degree} of a vertex \( x \in V(G) \) is defined as \( \deg x = \abs{N(x)} \).
\end{definition}
\begin{definition}
	Let \( G, H \) be graphs.
	A \emph{graph isomorphism} is a bijection \( \varphi \colon V(G) \to V(H) \) such that \( \qty{u,v} \in E(G) \iff \qty{\varphi(u),\varphi(v)} \in E(H) \).
\end{definition}
\begin{definition}
	We say \( H \) is a \emph{subgraph} of \( G \) if \( V(H) \subseteq V(G) \) and \( E(H) \subseteq E(G) \).
\end{definition}
If \( G \) is a graph, and \( xy \in E(G) \), we define \( G - xy \) to be the graph \( (V(G), E(G)\setminus \qty{xy}) \).
Similarly, for \( x, y \in V(G) \), we define \( G + xy \) to be the graph \( (V(G), E(G) \cup \qty{xy}) \).
\begin{definition}
	Let \( x, y \in V(G) \).
	A \emph{walk} from \( x \) to \( y \) in \( G \) is a sequence of vertices \( (x, \dots, y) \) such that each consecutive pair of elements of the sequence is connected by an edge in \( G \).
	A \emph{path} from \( x \) to \( y \) in \( G \) is a walk where all the vertices are disjoint.
\end{definition}
\begin{definition}
	A graph is \emph{connected} if every pair of vertices is connected with a path.
\end{definition}
The concatenation of two paths or walks \( P \) and \( P' \) is written \( PP' \).
\begin{remark}
	The concatenation of two walks is a walk.
	The concatenation of two paths is not necessarily a path, if the two paths share a vertex.
\end{remark}
\begin{proposition}
	If \( W \) is a \( x \)--\( y \) walk for \( x \neq y \), \( W \) contains a \( x \)--\( y \) path, where `contains' denotes a subsequence.
\end{proposition}
\begin{proof}
	Let \( W' \) be the minimal \( x \)--\( y \) walk in \( W \).
	This is a path, because if there were a repeated vertex, we could find a shorter path by eliminating the detour.
\end{proof}
\begin{definition}
	We define the \emph{distance} between two vertices, denoted \( d(x,y) \), to be the shortest length of a path between \( x \) and \( y \).
	If \( G \) is connected, this turns \( G \) into a metric space on its vertices.
\end{definition}

\subsection{Trees}
\begin{definition}
	A graph \( G \) is a \emph{acyclic} if it does not contain a cycle \( C_k \) as a subgraph.
	A graph \( G \) is a \emph{tree} if it is acyclic and connected.
\end{definition}
\begin{proposition}
	The following are equivalent.
	\begin{enumerate}
		\item \( G \) is a tree (acyclic and connected).
		\item \( G \) is \emph{minimally connected}: \( G \) is connected and for all \( xy \in E(G) \), \( G - xy \) is not connected.
		\item \( G \) is \emph{maximally acyclic}: \( G \) is acyclic and for all \( xy \not\in E(G) \), \( G + xy \) contains a cycle.
	\end{enumerate}
\end{proposition}
\begin{proof}
	\emph{(i) implies (ii).}
	Let \( xy \in E(G) \).
	Suppose \( G - xy \) were connected.
	Then there exists an \( x \)--\( y \) path \( P \) in \( G - xy \).
	We can then close up the path \( P \) into a cycle in \( G \) by adding the edge \( xy \).
	This contradicts the fact that \( G \) is acyclic.

	\emph{(ii) implies (i).}
	Suppose \( G \) has a cycle \( C \).
	Let \( xy \in E(C) \) be an edge in the cycle.
	We claim that \( G - xy \) is connected.
	Let \( P \) be a \( u \)--\( v \) path in \( G \).
	If \( P \) contains the edge \( xy \), replace the use of this edge with the remainder of the cycle, traversed in the opposite direction.
	This yields a \( u \)--\( v \) walk in \( G - xy \) which contains a \( u \)--\( v \) path.

	\emph{(i) implies (iii).}
	Let \( xy \not\in E(G) \).
	By connectedness, there exists an \( x \)--\( y \) path \( P \) in \( G \).
	Hence, adding \( xy \) to \( E(G) \), we obtain a cycle by concatenating \( P \) with \( xy \).

	\emph{(iii) implies (i).}
	Suppose \( G \) is not connected.
	Then there exist \( x \neq y \) such that there is no \( x \)--\( y \) path in \( G \).
	Hence, adding \( xy \) to \( E(G) \) cannot yield a cycle.
\end{proof}
\begin{definition}
	Let \( T \) be a tree.
	A \emph{leaf} of \( T \) is a vertex \( v \in V(T) \) where \( \mathrm{deg}(v) = 1 \).
\end{definition}
\begin{definition}
	Let \( G \) be a graph, and \( X \subseteq V(G) \).
	Then the \emph{graph induced on \( X \)}, denoted \( G[X] \) is the graph \( (X, \qty{xy \in E(G) \mid x \in X, y \in X}) \).
	If \( x \in G \), we define \( G - x \) to be the graph \( G[V(G) \setminus \qty{x}] \).
\end{definition}
\begin{proposition}
	Let \( T \) be a tree where \( \abs{T} \geq 2 \).
	Then \( T \) has a leaf.
\end{proposition}
\begin{proof}
	Let \( P = x_1, \dots, x_k \) be a longest possible path in \( T \).
	\( N(x_k) \subseteq \qty{x_1, \dots, x_{k-1}} \) by maximality of \( P \).
	If \( x_i \sim x_k \) for any \( 1 \leq i \leq k - 2 \), we have a cycle, which is a contradiction.
	Hence \( N(x_k) = \qty{x_{k-1}} \), so \( x_k \) is a leaf.
\end{proof}
\begin{remark}
	This proof actually demonstrates that any tree has at least two leaves, by considering \( x_1 \).
	We could alternatively have proven the lemma by taking a non-backtracking walk in \( G \), which exists assuming no leaf exists; then, since \( V(G) \) is finite, we must return to a point somewhere on the graph.
\end{remark}
\begin{proposition}
	Let \( T \) be a tree with \( n \geq 1 \) vertices.
	Then \( \abs{E(T)} = e(t) = n - 1 \).
\end{proposition}
\begin{proof}
	We prove this by induction on \( n \).
	The \( n = 1 \) case is trivial.
	Now, assume that all trees with \( n \) vertices have \( n - 1 \) edges, and suppose \( T \) has \( n + 1 \) vertices.
	\( T \) has a leaf \( x \).
	Then \( T - x \) is a tree with \( n \) vertices since it is still connected, and hence has \( n - 1 \) edges.
	Since \( T \) has one more edge than \( T - x \), namely the edge connecting the leaf \( x \) to \( T - x \), \( T \) has \( n \) edges as required.
\end{proof}
\begin{definition}
	Let \( G \) be a connected graph.
	Then a subgraph \( T \) of \( G \) is a \emph{spanning tree} if \( V(T) = V(G) \) and \( T \) is a tree.
\end{definition}
\begin{proposition}
	Every connected graph has a spanning tree.
\end{proposition}
\begin{proof}
	Begin with \( G \) and remove edges of \( E(G) \) such that the graph stays connected.
	When we can no longer remove edges, we must have a minimally connected subgraph of \( G \), and hence a tree.
\end{proof}

\subsection{Bipartite graphs}
\begin{definition}
	Let \( G = (V, E) \) be a graph.
	\( G \) is \emph{bipartite} if \( V = A \cup B \) where \( A \cap B = \varnothing \), such that all edges \( (x,y) \in E \) satisfy \( x \in A, y \in B \) or \( x \in B, y \in A \).

	The \emph{complete bipartite graph} on \( n \) and \( m \) vertices, denoted \( K_{n,m} \), is the bipartite graph with \( \abs{A} = n \), \( \abs{B} = m \) and with all possible edges.
\end{definition}
\begin{remark}
	Even cycles \( C_{2n} \) are bipartite, and odd cycles \( C_{2n+1} \) are not bipartite.
\end{remark}
\begin{definition}
	A \emph{circuit} is a sequence \( x_1, x_2, \dots, x_\ell, x_{\ell + 1} \) where \( x_i x_{i+1} \in E \) and \( x_{\ell + 1} = x_1 \).
	In other words, a circuit is a closed walk.
	The \emph{length} of this circuit is \( \ell \).
	A circuit is odd if its length is odd; a circuit is even if its length is even.
\end{definition}
\begin{proposition}
	Let \( C \) be an odd circuit in a graph \( G \).
	Then \( C \) contains an odd cycle.
\end{proposition}
\begin{proof}
	Let \( x_1, \dots, x_\ell, x_1 \) be an odd circuit.
	Either this is an odd cycle, or \( x_i = x_j \) for \( i < j \).
	Then \( x_i, \dots, x_j \) is a circuit and \( x_j, \dots, x_\ell, x_1, \dots, x_i \) is a circuit.
	Their lengths sum to \( \ell \), so one of them is odd.
	By induction, we can assume the odd circuit contains an odd cycle as required.
\end{proof}
\begin{theorem}
	Let \( G \) be a graph.
	Then \( G \) is bipartite if and only if \( G \) does not contain an odd cycle.
\end{theorem}
\begin{proof}
	If \( G \) contains an odd cycle, \( G \) is not bipartite because there exists a subgraph that is not bipartite.
	Suppose now that \( G \) contains no odd cycles.
	We may assume \( G \) is connected, because unions of disconnected bipartite graphs are bipartite.
	Let \( x_0 \in V(G) \).
	Let \( V_0 = \qty{x \in V(G) \mid d(x,x_0) \equiv 0 \text{ mod } 2} \) and \( V_1 = \qty{x \in V(G) \mid d(x,x_0) \equiv 1 \text{ mod } 2} \).
	We show that this is a bipartition as required.
	Suppose \( u, v \in V_i \) are connected.
	Then, \( u \) and \( v \) admit even (resp.\ odd) paths to \( x_0 \), so the circuit defined by the concatenation of these paths with the edge \( uv \) is an odd circuit, and hence contains an odd cycle.
	This contradicts our assumption.
\end{proof}

\subsection{Planar graphs}
\begin{definition}
	A \emph{plane graph} is a drawing of a graph in the plane, representing edges as piecewise linear functions, without edge crossings.
\end{definition}
\begin{definition}
	A graph \( G \) is \emph{planar} if it can be drawn in the plane \( \mathbb R^2 \) with no edges crossing, so a graph is planar if it admits a plane graph representation.
\end{definition}
\begin{example}
	\( K_1, K_2, K_3, K_4 \) are planar.
	\( P_n \) is planar for \( n \in \mathbb N \).
	\( K_{n,2} \) is planar, by placing the vertices in the two-vertex set on either side of the other set.
\end{example}
\begin{definition}
	Let \( G \) be a plane graph.
	One of the finitely many connected components of \( \mathbb R^2 \setminus G \) is called a \emph{face}.
	The boundary of a face \( F \) is the collection of vertices and edges in \( \partial f \).
	Therefore, the boundary of any face in \( G \) is a subgraph of \( G \).
\end{definition}
\begin{remark}
	The boundary of a face need not be (or contain) a cycle, and need not be connected.
	Two drawings of a graph can be fundamentally different.
\end{remark}
\begin{theorem}[Euler]
	Let \( G \) be a connected plane graph with \( F \) faces.
	Then \( \abs{V(G)} - \abs{E(G)} + F = 2 \).
\end{theorem}
\begin{remark}
	The number of faces is uniquely determined by intrinsic properties of a graph, its number of vertices and edges.
\end{remark}
\begin{proof}
	We work by induction on the number of edges \( E(G) \).
	In the case where \( E(G) = 0 \), we must have \( V(G) = 1 \) and \( F = 1 \) by connectedness.
	Suppose \( G \) is acyclic.
	Then by connectedness, \( G \) is a tree, so \( V(G) = E(G) + 1 \) and \( F = 1 \), satisfying Euler's formula.
	Now suppose \( G \) contains a cycle, and \( E \) be an edge in the cycle.
	Removing this edge, \( G - E \) is connected, and has \( \abs{V(G)} \) vertices, \( \abs{E(G)} - 1 \) edges, and \( F - 1 \) faces.
	By induction, Euler's formula holds in this case.
\end{proof}
\begin{corollary}
	Let \( G \) be a planar graph where \( \abs{G} \geq 3 \).
	Then \( e(G) \leq 3\abs{G} - 6 \).
\end{corollary}
\begin{proof}
	Consider a planar drawing of \( G \).
	We may assume \( G \) is connected without loss of generality.
	Let \( F \) be a face, and let \( \deg F \) be the number of edges that meet at \( F \).
	Note that the degree of any face is at least 3, since \( \abs{G} \geq 3 \).
	Since each edge occurs in at most two faces, \( \sum_F \deg F \leq 2e(G) \).
	Hence, \( 3f \leq 2e(G) \), where \( f \) is the amount of faces.
	Using Euler's formula, \( \abs{G} - e(G) + f = 2 \implies 2(\abs{G} - 2) \geq e(G) \).
\end{proof}
\begin{remark}
	\( K_5 \) is not planar, because \( e(K_5) = 10 \) and \( 3 \abs{K_5} - 6 = 9 \).
	\( K_{3,3} \) does not violate this bound, but is not planar.
\end{remark}
\begin{corollary}
	Let \( G \) be a planar graph, \( \abs{G} \geq 4 \) and there is no cycle of length 3.
	Then \( e(G) \leq 2(\abs{G} - 2) \).
\end{corollary}
\begin{proof}
	The minimal degree of a face is 4, because a degree of 3 would imply there is a triangle since there are at least four vertices in the graph.
	Running the same argument, our bound becomes \( e(G) \leq 2(\abs{G} - 2) \),
\end{proof}
This shows that \( K_{3,3} \) is not planar.
\begin{definition}
	A \emph{subdivision} of a graph \( G \) is a new graph where some of the edges are replaced by (disjoint) paths.
\end{definition}
\begin{remark}
	A subdivision of a non-planar graph is non-planar.
	In particular, if \( G \) contains a subdivision of \( K_{3,3} \) or \( K_5 \), \( G \) is non-planar.
\end{remark}
\begin{theorem}[Kuratowski]
	\( G \) is planar if and only if it contains no subdivision of \( K_{3,3} \) or \( K_5 \).
\end{theorem}
